package com.leetcode.algorithm.y22.m09.w2;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 763. 划分字母区间
 * 
 * https://leetcode.cn/problems/partition-labels/
 * 
 * @author jie.deng
 *
 */
class Question0763Solution02 {
	
	public List<Integer> partitionLabels(String s) {
		List<Integer> list = new ArrayList<>();

		int len = s.length();
		// 统计每一个字符最后出现的位置
		int[] lastIdxArr = new int[26];
		Arrays.fill(lastIdxArr, -1);

		for (int i = len - 1; i >= 0; i--) {
			int idx = s.charAt(i) - 'a';
			if (lastIdxArr[idx] == -1) {
				lastIdxArr[idx] = i;
			}
		}

		int fromIdx = 0;
		int toIdx = -1;
		for (int i = 0; i < len; i++) {
			int idx = s.charAt(i) - 'a';
			if (lastIdxArr[idx] > toIdx) {
				toIdx = lastIdxArr[idx];
			}
			if (i == toIdx) {
				list.add(i - fromIdx + 1);
				fromIdx = i + 1;
			}
		}
		return list;
	}
    
}